//1、	桶排序：适合用在外部排序中，即数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
//n个数，分到m个桶，平均下来每个桶里有k= n/m个元素，每个桶用快排，时间复杂度O(klogk)，m个桶就是O(m*klogk),带入k，
//时间复杂度是O(n*logn/m),当m很大时候，就是O（n）。若只有一个桶，则退化为O(nlogn)。
//桶排序  参数：arr，桶的大小，每个桶装几个buckedSize
function bucketSort(arr, buckedSize) {
    if (arr.length < 2) {
        return arr
    }
    let buckets = getBuckets(arr, buckedSize);//计算出桶的个数
    return sortBuckets(buckets);
}

//把所有数据放入桶中，桶为数组，第几个桶，每个桶里放的数据也是数组，所以是二维数组
function getBuckets(arr, buckedSize) {
    //1、找到minValue,maxValue,计算出桶的个数bucketCount
    let minValue = arr[0];
    let maxValue = arr[0];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < minValue) {
            minValue = arr[i];
        } else if (arr[i] > maxValue) {
            maxValue = arr[i];
        }
    }
    const bucketCount = Math.floor((maxValue - minValue) / buckedSize) + 1;

    //2、桶是一个数组，每个桶里又是一个数组
    let buckets = [];
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }
    //3、放入数据
    for (let i = 0; i < arr.length; i++) {
        let index = Math.floor((arr[i] - minValue) / buckedSize);
        buckets[index].push(arr[i]);
    }
    return buckets;
}


function sortBuckets(bucketCount) {

    //4、循环排序，然后复制
    let result = [];
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i]);
            result = result.concat(buckets[i]);
        }

    }
    return result;
}

//插入排序
function insertionSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    for (let i = 1; i < arr.length; i++) {
        const value = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > value) {
            arr[j + 1] = a[j];
            j--;
        }
        arr[j] = value;
    }
}